#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        int m = n * 2;
        vector<string> res;
        string s(m, 0);
        auto dfs = [&](auto&& dfs, int u, int l) {
            if (u == m)
            {
                res.push_back(s);
                return;
            }
            if (l < n)
            {
                s[u] = '(';
                dfs(dfs, u + 1, l + 1);
            }
            if (u - l < l)
            {
                s[u] = ')';
                dfs(dfs, u + 1, l);
            }
            };
        dfs(dfs, 0, 0);
        return res;
    }
};